package com.tang.algorithm.swordFingerOffer;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author tlm
 * @version 1.0
 * @date 2020/5/9 20:28
 * 数组中出现次数超过一半的数字
 * <p>
 * https://leetcode-cn.com/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
 */
public class MoreThanHalfOfArray {
    public static void main(String[] args) {
        MoreThanHalfOfArray test = new MoreThanHalfOfArray();
        int[] a = {1};
        System.out.println(test.majorityElement(a));
    }

    /**
     * 解法1，哈希表统计法
     *
     * @param nums
     * @return
     */
    public int majorityElement(int[] nums) {
        if (nums.length == 1) {
            return nums[0];
        }
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int key = nums[i];
            if (hashMap.containsKey(key)) {
                int value = hashMap.get(key);
                hashMap.put(key, ++value);
                if (value > nums.length / 2) {
                    return nums[i];
                }
            } else {
                hashMap.put(key, 1);
            }
        }

        return 0;
    }

    /**
     * 解法2，数组排序法： 将数组 nums 排序，由于众数的数量超过数组长度一半，因此 数组中点的元素 一定为众数。
     */
    public int majorityElement2(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }

    /**
     * 解法3，摩尔投票法： 核心理念为 “正负抵消”
     */
    public int majorityElement3(int[] nums) {
        int x = 0, votes = 0;
        for (int num : nums) {
            if (votes == 0) {
                x = num;
            }
            votes += num == x ? 1 : -1;
        }
        return x;
    }
}
